Object-oriented languages are well established. Many such languages exist, each having their own syntax. However, the essential concepts underlying these languages are very similar. In general terms, object oriented languages involve the creation of data structures known as objects, which are instances of a particular class or type. A class is associated with instance variables, also referred to as members, as well as methods or functions. A class can have subclasses and/or superclasses, and the resulting structure is referred to as a class hierarchy. For example, FIG. 1 illustrates a simple class hierarchy in which classes Y 20 and Z 30 are subclasses of class X 10. Y and Z can also be referred to as being derived from class X. Class X is referred to as the superclass or baseclass of classes Y and Z.
Class X is shown as defining members I 11 and J 12 and methods M( ) 13 and N( ) 14. Class Y has member K 21 and defines methods M( ) 23 and P( ) 24. Class Z has member L 31 and defines method R( ) 34.
FIG. 1 shows that class Y 20 implements its own version of method M( ). The method M 23 defined in class Y 20 is said to override method M( ) 13 in class X 10. Since the actual method being called (either M( ) 13 or M( ) 23) will depend on the type of the calling object, which will only be determined at run-time, a technique known as dynamic dispatch, the method M( ) is referred to as a virtual function. In the C++ computer language, for example, a method which has several implementations and needs to be selected dynamically is explicitly declared in the baseclass as a virtual function.
Access to virtual functions is generally carried out through data structures known as virtual tables, or vtables, which are created by a compiler. This access carries a significant run-time penalty as compared with direct function calls. This presents a problem since virtual function calls are widely used in languages such as C++ and can therefore significantly affect the performance of programs written in this language.
Function devirtualization is a well-known compiler optimization technique for programs written in languages that make use of virtual functions. This optimization replaces a call to a virtual function by a call to a particular function of a class, so eliminating the overheads of accessing a virtual function via virtual tables. In addition, the direct call may be inlined, giving rise to the possibility of further performance improvements.
Function devirtualization can be understood by reference to Listing 1 below.
Listing 1.class A {    int i;public:    A( ):i(0){ };    ~A( ){ };    virtual int get_val( ) {return i;};};class B : public A{    int j;public:    B( ):j(45){ };    ~B( ){ };}int foo(void){    B b, *bp;    bp=&b;    return bp−>get_val( );}
In Listing 1, the call to get_val( ) in foo( ) is a call to an object of class B. Since class B is declared to be derived from class A (class B: public A { . . . }), but does not include a method named get_val( ), the call to get_val( ) therefore actually calls the function get_val( ) of class A. Normally, such virtual function calls are executed by using the virtual table pointers. These not only add overhead to the calling mechanism but also block any form of inlining possible at the call point. In this example, the call to get_val( ) can be replaced by a direct call to get_val( ) of class A in the following manner:
return bp→A::get_val( );
However, to devirtualize automatically in a compiler at static time requires knowledge of class hierarchy, namely which subclasses have virtual functions that override those declared in their superclasses/baseclasses. For the example being considered, the call to get_val( ) can be rerouted to a call to A::get_val( ) by noting that class B does not override the virtual method named get_val( ) defined in its baseclass, class A. This analysis is termed the Class Hierarchy Analysis (CHA).
Class Hierarchy Analysis (CHA) is one of the well-known techniques that are applied to find out whether a virtual call is devirtualizable.
The building block of CHA is the Class Hierarchy Graph (CHG). The Class Hierarchy Graph contains nodes, each of which represent a class, and edges, each of which represent a superclass-subclass relationship i.e. if an edge points from node x to node y, then x is the superclass and y the subclass. In addition, each node has a list of virtual functions defined in the class. For the example given in Listing 1, the Class Hierarchy Graph is as shown in FIG. 2.
FIG. 2 shows that both classes A 40 and B 50 access the same get_val function, A::get_val 60, as get_val( ) defined in class A is not overridden in class B.
Building the Class Hierarchy Graph is straightforward when all the class definitions are visible in a single file. The situation becomes more complicated when the derived classes and the base classes are in different files and the Class Hierarchy Graph needs to be constructed. In such cases, the compiler usually depends on a feature whereby all the compilation units are visible, for example, under the option -ipo for Intel and HP compilers or +O4 or +Owhole_program_mode for many other compilers. Listing 2 is an example to illustrate this point. Class A is defined in file f1.C, while the derived class B is in f2.C. In addition, f1.C defines a function DoSomething( ) that takes a parameter that is a pointer to an object of type A.
Listing 2.#include “f1.H”int DoSomething( A *pa) { // Cannot replace get_val with A::get_val DoSomethingElse(pa−>get_val( ));}   <file f1.C>#include “f1.H”class B: public A { int j;public: B( ): j(0) { }; ~B( ) { }; virtual int get_val( ) { return j+2; };};  <file f2.C>class A { int i;public: A( ): i(0) { }; ~A( ) { }; virtual int get_val( ) { return i; };};  < file f1.H>
Class B in file f2.C overrides the function get_val( ) defined in class A of f1.C. Hence, the Class Hierarchy Graph of FIG. 1 would change to the one in FIG. 3. In this case, Class A 40 and Class B 50 access different get_val( ) functions 62, 64 respectively.
It would now be impossible (statically) to infer from the Class Hierarchy Graph that the call to pa→get_val( ) in DoSomething( ) can be replaced by pa→A::get_val( ). This is because a call to DoSomething( ) can pass either objects of type A 40 or of type B 50 to the function as actual parameters. If an object of type B 50 is passed, replacing the virtual call by a call to A::get_val( ) will result in incorrect code.